#ifndef CYBER_DASH_LINK_QUEUE_H
#define CYBER_DASH_LINK_QUEUE_H

#include <cstdlib>
using namespace std;

template <class T>  //使用模板
class LinkNode      //节点类，节点包含 值、节点指针
{
public:
    //构造函数，队列首个值无需指向后面的节点（应为就一个值），指针为空
    explicit LinkNode(LinkNode<T>* ptr = NULL): link_(ptr) {}
    explicit LinkNode(const T& data, LinkNode<T> *ptr = NULL): data_(data), link_(ptr) {}

    T GetData() { return data_; } //获取节点值
    bool SetData(const T& data) { data_ = data; return true; }    //设置节点值

    LinkNode<T>* GetLink() { return link_; }  //获取该节点后面节点的指针
    bool SetLink(LinkNode<T>* ptr) { link_ = ptr; return true; }  //设置该节点后面节点的指针
private:
    T data_;              //节点值
    LinkNode<T> *link_;   //指向后面节点的指针
};


template<class T>
class LinkQueue
{
public:
    LinkQueue();
    ~LinkQueue();
    bool EnQueue(const T& data);    //压入队列
    bool DeQueue(T& data);          //队列取值
    bool GetFront(T& data) ;   //取队列首个值，并不释放首节点内存
    bool IsEmpty() ;       //判断队列是否为空
    int GetSize() ;        //获取队列大小
    void MakeEmpty();           //清空队列

    LinkNode<T>* GetFrontPtr() { return front_ptr_; }   //获取首个节点指针
    LinkNode<T>* GetRearPtr() { return rear_ptr_; }     //获取尾部节点指针

private:
    LinkNode<T>* front_ptr_;    //首部指针
    LinkNode<T>* rear_ptr_;     //尾部指针
};

template<class T>
LinkQueue<T>::LinkQueue()
{
    front_ptr_=NULL;
    rear_ptr_=NULL;
}

template<class T>
LinkQueue<T>::~LinkQueue()
{
    MakeEmpty();
}

template<class T>
bool LinkQueue<T>::EnQueue(const T& data)
{
    LinkNode<T>* new_node_ptr = new LinkNode<T>(data);
    if (new_node_ptr == NULL)
        return false;

    if (IsEmpty()) //如果队列为空，则该节点为首位节点
    {
        front_ptr_ = new_node_ptr;
        rear_ptr_ = new_node_ptr;
    }
    else
    {
        rear_ptr_->SetLink(new_node_ptr);   //尾部节点指向新的节点
        rear_ptr_ = new_node_ptr;   //更新尾部指针
    }
    return true;
}

template<class T>
bool LinkQueue<T>::DeQueue(T& data)
{
    if (IsEmpty())    //如果队列为空则操作失败
        return false;
    LinkNode<T>* cur_ptr = front_ptr_;
    data = cur_ptr->GetData();
    front_ptr_ = front_ptr_->GetLink();   //更新首部指针
    delete cur_ptr;   //释放原来的首部节点内存
    return true;
}

template<class T>
bool LinkQueue<T>::GetFront(T& data)
{
    if (IsEmpty())
        return false;
    data = front_ptr_->GetData();
    return true;
}

template<class T>
bool LinkQueue<T>::IsEmpty()
{
    return front_ptr_ == NULL;   //直接判断指向首结点的指针是否为空
}

template<class T>
int LinkQueue<T>::GetSize()
{
    int count = 0;
    LinkNode<T>* cur_ptr = front_ptr_;
    //一直从首节点访问到尾节点
    while (cur_ptr != NULL)
    {
        cur_ptr = cur_ptr->GetLink();
        count++;
    }
    return count;
}

template<class T>
void LinkQueue<T>::MakeEmpty()
{
    LinkNode<T>* cur_ptr;
    while (front_ptr_ != NULL)  //从首节点清空到尾部
    {
        cur_ptr = front_ptr_;
        front_ptr_ = front_ptr_->GetLink();
        delete  cur_ptr;
    }
}


#endif //CYBER_DASH_LINK_QUEUE_H
